//
//  LRUAndLFU.hpp
//  leetcode
//
//  Created by Ellie on 2021/2/19.
//  Copyright © 2021 Ellie. All rights reserved.
//

#ifndef LRUAndLFU_hpp
#define LRUAndLFU_hpp

#include <stdio.h>
#include <list>
#include <unordered_map>

using namespace std;

// Define LRU and LFU

//
// LRU(Least Recently Useds) Discards the least recently used items first. Time order
//

// get O(1)
// put O(1)

// HashMap + Double LinkedList(core)
// Double LinkedList constants time delete and insert O(1)
// HashMap constants time find O(1)

// C++ std::list is doubly-linkedlist

// 使用C++中标准库中的双链表+hashmap实现
// 内存占用比较高，面试中需要自己实现DoublyList然后借助C++的hashmap实现LRU算法

class LRUCache {
private:
    int size;
    // lru list
    // ordered list (last element is least recently used, when full remove back() element)
    std::list<int> lru;
    // key -> find interator in lru list
    unordered_map<int, std::list<int>::iterator> cachelistmap;
    // key -> value find value with given key
    unordered_map<int, int> cache;
public:
    LRUCache(int capacity) {
        size = capacity;
    }
    
    int get(int key) {
        if(cache.find(key) == cache.end())
        {
            return -1;
        }
        updateLRU(key);
        return cache[key];
    }
    
    void put(int key, int value) {
        if(cache.size() == size && (cache.find(key) == cache.end()))
        {
            evict();
        }
        updateLRU(key);
        cache[key] = value;
    }
    
    void updateLRU(int key){
        if(cache.find(key) != cache.end())
        {
            lru.erase(cachelistmap[key]);
        }
        lru.push_front(key);
        cachelistmap[key] = lru.begin();
    }
    
    // evict the least recently used key.
    void evict(){
        cache.erase(lru.back());
        cachelistmap.erase(lru.back());
        lru.pop_back();
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

// HARD
// LFU Least Frequently Used (LFU) is a type of cache algorithm used to manage memory within a computer. The standard characteristics of this method involve the system keeping track of the number of times a block is referenced in memory. When the cache is full and requires more room the system will purge the item with the lowest reference frequency.

// get O(1)
// put O(1)
// 增加一个使用频次维度
class LFUCache {
public:
    LFUCache(int capacity) {
    }
    
    int get(int key) {
        return 0;
    }
    
    void put(int key, int value) {
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

#endif /* LRUAndLFU_hpp */
